import java.util.Scanner;

public class Main {

public int minDistance(String word1, String word2) {
        int m=word1.length()-1,n=word2.length()-1;//指向数组的最后一个元素
        return dp(word1, m, word2, n);
    }
public int dp(String s1,int i,String s2,int j) {
	if(i==-1) return j+1;
	if(j==-1) return i+1;
	
	if(s1.charAt(i)==s2.charAt(j)) {
		return dp(s1, i-1, s2, j-1);//相同，啥都不做，往前移一步
	}
	
	return min(
			dp(s1, i, s2, j-1)+1,//插入一个字符
			dp(s1, i-1, s2,j),//删除一个字符
			dp(s1, i-1, s2, j-1)//替换一个字符
			);
}

public int min(int a,int b,int c) {
	return Math.min(a, Math.min(b, c)));
}
}
